#include <stdio.h>
#include <stdlib.h>

struct PageNode
{
	int value;
	struct PageNode *next;
};

int N = 247573;
int PageOutDegree[247573];
int PageInDegree[247573];
struct PageNode PageInLink[247573];
struct PageNode PageOutLink[247573];
int VisitOrder[247573];
int VisitFlag[247573];
int SCC[247573];
int WCC[247573];

void VisitOne(int cur,int *order,int *setIndex)
{
	VisitFlag[cur] = 1;
	WCC[cur] = *setIndex;
	struct PageNode *node = &PageOutLink[cur];
	while(node->value != -1)
	{
		if(VisitFlag[node->value] == 0)
			VisitOne(node->value,order,setIndex);
		node = node->next;
	}
	VisitOrder[*order] = cur;
	(*order)++;
}

void VisitTwo(int cur, int *order)
{
	VisitFlag[cur] = 1;
	SCC[cur] = *order;
	struct PageNode *node = &PageInLink[cur];
	while(node->value != -1)
	{
		if (VisitFlag[node->value] == 0)
			VisitTwo(node->value,order);
		node = node->next;
	}
}

int comp(const void *a,const void *b)
{
	return *(int *)b - *(int *)a;
}

int main()
{
	char line[1000];
	char *cTemp;
	int i,j,k,a,b,c,t,n,bool,lineNumber;
	int ***data = malloc(sizeof(int**)*28);
	struct PageNode *node[N];
	struct PageNode *temp;
	int CoreTotal = 0;
	int InTotal = 0;
	int OutTotal = 0;
	int WCCSetN = 37366;	////共有这么多的弱连通子集
	int WCCSet[WCCSetN];
	int SCCSetN = 111451;	//共有这么多的强连通子集
	int SCCSet[SCCSetN];
	int WCCRankMax = 91308;
	int SCCRankMax = 12988;
	int WCCRank[WCCRankMax];		//弱连通子集的大小最大为91308
	int SCCRank[SCCRankMax];		//强连通子集的大小最大不超过12988;
	FILE *fr,*fw;
	/**数据初始化**/
	for(i = 0;i < 30;i++)
	{
		data[i] = malloc(sizeof(int *)*50);
		for(j = 0;j < 50;j++)
		{
			data[i][j] = malloc(sizeof(int)*900);
			for(k = 0;k < 900;k++)
				data[i][j][k] = -1;
		}
	}
	for(i = 0;i < N;i++)
	{
		PageOutDegree[i] = 0;
		PageInDegree[i] = 0;
		PageOutLink[i].value = -1;		
		PageInLink[i].value = -1;
		node[i] = &PageOutLink[i];
	}
	for(i = 0;i < WCCSetN;i++)
		WCCSet[i] = 0;
	for(i = 0;i < SCCSetN;i++)
		SCCSet[i] = 0;
	for(i = 0;i < WCCRankMax;i++)
		WCCRank[i] = 0;
	for(i = 0;i < SCCRankMax;i++)
		SCCRank[i] = 0;
	/**读取并初步处理数据**/	
	fr = fopen("wt2g_inlinks","r");
	t = 0;
	while (fgets(line,1000,fr) != NULL)
	{
		cTemp = line;
		bool = 0;	
		while(sscanf(cTemp,"WT%d-B%d-%d %n",&a,&b,&c,&n) != EOF)
		{
			cTemp += n;
			if(data[a][b][c] == -1)
			{
				data[a][b][c] = t;
				t++;
			}
			if(bool == 0)
			{
				bool = 1;
				lineNumber = data[a][b][c];
				temp = &PageInLink[lineNumber];
			}
			else
			{
				PageInDegree[lineNumber]++;
				temp->value = data[a][b][c];
				temp->next = malloc(sizeof(struct PageNode));
				temp = temp->next;
				temp->value = -1;
				PageOutDegree[data[a][b][c]]++;	//处理OutDegree
				node[data[a][b][c]]->value = lineNumber;//连接结构
				node[data[a][b][c]]->next = malloc(sizeof(struct PageNode));
				node[data[a][b][c]] = node[data[a][b][c]]->next;
				node[data[a][b][c]]->value = -1; // 如果是没有其他网页链接到该网页，设该网页的value为-1。
			}
		}
	}
	int order,setIndex;
	/**处理WCC节点**/
	for(i = 0;i < N;i++)
		VisitFlag[i] = 0;
	order = 0;setIndex = 0;
	for(i = 0; i < N; i++)
		if (VisitFlag[i] == 0)
		{
			VisitOne(i,&order,&setIndex);
			setIndex++;
		}
	/**处理SCC节点**/
	for(i = 0;i < N;i++)
		VisitFlag[i] = 0;
	order = 0;setIndex = 0;
	for(i = N-1; i >= 0; i--)
		if (VisitFlag[VisitOrder[i]] == 0)
		{
			VisitTwo(VisitOrder[i],&setIndex);
			setIndex++;
		}
	/**对SCC和WCC节点进行整理**/
	for(i = 0;i < N;i++)
	{
		SCCSet[SCC[i]]++;
		WCCSet[WCC[i]]++;
	}
	/**根据子集大小进行排序**/
	qsort(SCCSet,SCCSetN,sizeof(int),comp);
	qsort(WCCSet,WCCSetN,sizeof(int),comp);
	/**记录每种大小的集合个数**/
	for(i = 0;i < SCCSetN;i++)
		SCCRank[SCCSet[i]-1]++;
	for(i = 0;i < WCCSetN;i++)
		WCCRank[WCCSet[i]-1]++;
	/**领结结构的Core**/
	for(i = 1;i < SCCRankMax;i++)
		CoreTotal += (i + 1)*SCCRank[i];
	/**领结结构的In和Out部分**/
	for(i = 0;i < N;i++)
	{
		if(PageInDegree[i] != 0 && PageOutDegree[i] == 0)
			InTotal++;
		else if(PageInDegree[i] == 0 && PageOutDegree[i] != 0)
			OutTotal++;
	}
	printf("In Part: %lf\n",(double)InTotal/N);
	printf("Core Part: %lf\n",(double)CoreTotal/N);
	printf("Out Part: %lf\n",(double)OutTotal/N);
	/**输出WCC和SCC**/
	fw = fopen("../res/Connectivity_WCC_Result","w");
	for(i = 0;i < WCCRankMax;i++)
		fprintf(fw,"%d\n",WCCRank[i]);
	fclose(fw);
	fw = fopen("../res/Connectivity_SCC_Result","w");
	for(i = 0;i < SCCRankMax;i++)
		fprintf(fw,"%d\n",SCCRank[i]);
	fclose(fw);		
	return 0;
}
